Within a data processing system there may be the need for certain data which is generated or received to be stored in a data store. In order to limit the space occupied in the data store by this data it may be compressed before being stored. The need to perform this data compression may be particularly acute in the case of a small data processing system with only limited storage capacity. However such a small data processing system may also have limited processing capability and a limited power supply, so that data compression represents a task burden requiring careful management.